package leecode.array.二分查找问题;

/**
 * @author wangxi created on 2021/10/30 19:22
 * @version v1.0
 * https://leetcode-cn.com/problems/search-a-2d-matrix/submissions/
 */
public class SearchMatrix {

    public static void main(String[] args) {
        int[][] matrix = {{1},{3}};
        SearchMatrix obj = new SearchMatrix();
        //obj.searchMatrix(matrix, 3);
    }

    /**
     * 注意：这个的条件和  SearchMatrixII 的条件不一致。这个限制了下一行的每个元素肯定比上一行大。
     * 但是 SearchMatrixII 这个就不一定了，所以这个就不能使用行列二分。
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length <= 0 || matrix[0].length <= 0) {
            return false;
        }
        // 先对列二分，定位是哪一行，因为第一列是升序的，定位到具体的行，必然就能肯定这行如果没有，那结果就是false
        int firstCol = searchFirstCol(matrix, target);
        if (firstCol == -1) {
            return false;
        }
        if (matrix[firstCol][0] == target) {
            return true;
        }
        return searchRow(matrix[firstCol], target);
    }

    private boolean searchRow(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }

    private int searchFirstCol(int[][] matrix, int target) {
        int left = 0;
        int right = matrix.length - 1;
        if (target > matrix[matrix.length - 1][0]) {
            return matrix.length - 1;
        }
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (matrix[mid][0] == target || (mid < matrix.length - 1 && target > matrix[mid][0] &&
                    target < matrix[mid + 1][0])) {
                return mid;
            } else if (matrix[mid][0] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
